<html>
<head><meta charset="utf-8"><title>Syntax highlighting is quadratic · t-compiler/rust-analyzer · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/index.html">t-compiler/rust-analyzer</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html">Syntax highlighting is quadratic</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="240872232"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/240872232" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#240872232">(May 31 2021 at 21:22)</a>:</h4>
<p>So after commenting a few things out here and there it seems that the culprit is the doc highlight injection</p>



<a name="240872310"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/240872310" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#240872310">(May 31 2021 at 21:22)</a>:</h4>
<p>numstructs milliseconds</p>
<div class="codehilite"><pre><span></span><code>1000 827
2000 1890
3000 3165
4000 4755
5000 6555
6000 8574
7000 10677
8000 13144
</code></pre></div>
<p>This is what I get when I just comment the injection out</p>



<a name="240872372"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/240872372" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#240872372">(May 31 2021 at 21:23)</a>:</h4>
<p>Which is already a lot faster than with it uncommented</p>



<a name="240872991"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/240872991" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#240872991">(May 31 2021 at 21:33)</a>:</h4>
<p>With just calling <a href="https://github.com/rust-analyzer/rust-analyzer/blob/71117e6812f87e014bc8e984e195a75e222ac227/crates/ide/src/doc_links.rs#L173-L198"><code>doc_attributes</code></a> in the injection code and returning afterwards I get</p>
<div class="codehilite"><pre><span></span><code>1000 1556
2000 3737
3000 6653
4000 10340
5000 14573
6000 19411
</code></pre></div>
<p><del>Adding the <a href="https://github.com/rust-analyzer/rust-analyzer/blob/71117e6812f87e014bc8e984e195a75e222ac227/crates/hir_def/src/attr.rs#L452-L503"><code>attributes.docs_with_rangemap</code></a> call to that gives:</del><br>
<del><code>
1000 2343
2000 6425
3000 12279
4000 19838
5000 29203
6000 40330
</code></del><br>
Note that the only comments in the test fixture are single line doc comments on the generated fields<br>
<span aria-label="grimacing" class="emoji emoji-1f62c" role="img" title="grimacing">:grimacing:</span></p>



<a name="240874736"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/240874736" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#240874736">(May 31 2021 at 22:00)</a>:</h4>
<p>Adding the <a href="https://github.com/rust-analyzer/rust-analyzer/blob/71117e6812f87e014bc8e984e195a75e222ac227/crates/hir_def/src/attr.rs#L368-L450"><code>attributes.source_map</code></a> call in gives:</p>
<div class="codehilite"><pre><span></span><code>1000 2323
2000 5880
3000 11172
4000 18011
5000 26117
6000 35742
</code></pre></div>



<a name="240875087"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/240875087" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#240875087">(May 31 2021 at 22:06)</a>:</h4>
<p>I fail to see where all ofthis is getting quadratic in regards to the fields though <span aria-label="confused" class="emoji emoji-1f615" role="img" title="confused">:confused:</span><br>
Maybe this isn't the quadratic cause but just something that gets caught up in it? Since the first timings are still somewhat quadratic looking</p>



<a name="240917064"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/240917064" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Laurențiu <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#240917064">(Jun 01 2021 at 09:37)</a>:</h4>
<p><span class="user-mention silent" data-user-id="300586">Lukas Wirth</span> <a href="#narrow/stream/185405-t-compiler.2Frust-analyzer/topic/Syntax.20highlighting.20is.20quadratic/near/240872310">said</a>:</p>
<blockquote>
<p>numstructs milliseconds</p>
<div class="codehilite"><pre><span></span><code>1000 827
2000 1890
3000 3165
4000 4755
5000 6555
6000 8574
7000 10677
8000 13144
</code></pre></div>
<p>This is what I get when I just comment the injection out</p>
</blockquote>
<p>But that's already quadratic, so maybe it's not the highlight injection.</p>



<a name="240917394"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/240917394" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> pachi <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#240917394">(Jun 01 2021 at 09:40)</a>:</h4>
<p>That's almost linear, 2ms for each new struct (1000 new structs -&gt; 2000 more ms).</p>



<a name="240917686"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/240917686" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#240917686">(Jun 01 2021 at 09:43)</a>:</h4>
<p><span class="user-mention silent" data-user-id="203546">Laurențiu</span> <a href="#narrow/stream/185405-t-compiler.2Frust-analyzer/topic/Syntax.20highlighting.20is.20quadratic/near/240917064">said</a>:</p>
<blockquote>
<p><span class="user-mention silent" data-user-id="300586">Lukas Wirth</span> <a href="#narrow/stream/185405-t-compiler.2Frust-analyzer/topic/Syntax.20highlighting.20is.20quadratic/near/240872310">said</a>:</p>
<blockquote>
<p>numstructs milliseconds</p>
<div class="codehilite"><pre><span></span><code>1000 827
2000 1890
3000 3165
4000 4755
5000 6555
6000 8574
7000 10677
8000 13144
</code></pre></div>
<p>This is what I get when I just comment the injection out</p>
</blockquote>
<p>But that's already quadratic, so maybe it's not the highlight injection.</p>
</blockquote>
<p>Ye that was what I meant with my last message. It just wasnt too obvious to me at first, but I feel like the "quadratic-ness" got worse with the injection stuff?</p>



<a name="240917799"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/240917799" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dawer <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#240917799">(Jun 01 2021 at 09:44)</a>:</h4>
<p>Can field resolution cause this? <a href="https://github.com/rust-analyzer/rust-analyzer/pull/9031#issuecomment-851409380">https://github.com/rust-analyzer/rust-analyzer/pull/9031#issuecomment-851409380</a></p>



<a name="240917917"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/240917917" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#240917917">(Jun 01 2021 at 09:45)</a>:</h4>
<p>Noh the generated fixture is only struct definitions so those arent revelant(I also checked just in case and commented the parts out)</p>



<a name="240917943"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/240917943" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#240917943">(Jun 01 2021 at 09:45)</a>:</h4>
<p>Those are still quadratic though with their lookup, its just not the main problem here</p>



<a name="240918147"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/240918147" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#240918147">(Jun 01 2021 at 09:47)</a>:</h4>
<p><a href="/user_uploads/4715/T53Lv39yLaAtfGmuIzUsREjo/image.png">image.png</a> </p>
<div class="message_inline_image"><a href="/user_uploads/4715/T53Lv39yLaAtfGmuIzUsREjo/image.png" title="image.png"><img src="/user_uploads/4715/T53Lv39yLaAtfGmuIzUsREjo/image.png"></a></div><p>This is the plot. It is slightly slower than linear. Maybe O(n log n)?</p>



<a name="241090957"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/241090957" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Mario Carneiro <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#241090957">(Jun 02 2021 at 00:04)</a>:</h4>
<p>Actually if you plot <code>x, y/x</code> it's pretty linear, it just that the quadratic factor is fairly small compared to the linear component. Best fit is about <code>0.73 n + 0.00011 n^2</code></p>



<a name="241790551"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/241790551" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#241790551">(Jun 07 2021 at 15:06)</a>:</h4>
<p>Oh I forgot about this <span aria-label="sweat smile" class="emoji emoji-1f605" role="img" title="sweat smile">:sweat_smile:</span> I'm still not entirely sure whats going on here but I think the <code>sema.to_def</code> call is quadratic for fields?</p>



<a name="241790815"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/241790815" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#241790815">(Jun 07 2021 at 15:07)</a>:</h4>
<p>Iirc when looking for definitions we search for the container, which is the struct for fields and then search linearly in the container for  the index or something which would be certainly quadratic. This is just a guess though I haven't looked much into how we map ast things to definitions yet</p>



<a name="241795189"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/241795189" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#241795189">(Jun 07 2021 at 15:34)</a>:</h4>
<p><code>record_field_to_def</code> seems to go through <code>DynMap</code> like other items</p>



<a name="241796025"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/241796025" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#241796025">(Jun 07 2021 at 15:39)</a>:</h4>
<p>hmm, and the <code>HasChildSource</code> code in <code>adt.rs</code> looks linear in the size of the struct from what I can tell</p>



<a name="241796145"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/241796145" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#241796145">(Jun 07 2021 at 15:40)</a>:</h4>
<p>and since this is cached we should only compute it once per struct, and then do <code>O(1)</code> lookups in the map</p>



<a name="241806049"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/241806049" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#241806049">(Jun 07 2021 at 16:49)</a>:</h4>
<p>Hmm ye that doesn't seem to be it then...</p>



<a name="241854343"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/241854343" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#241854343">(Jun 07 2021 at 23:28)</a>:</h4>
<p>I'm pretty sure that highlighting <em>within macros</em> is quadratic though: <code>TokenMap</code> lookups are linear in the size of the input (I think), and highlighting does it once per input token</p>



<a name="242794136"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/242794136" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#242794136">(Jun 15 2021 at 20:23)</a>:</h4>
<p><del>Im looking into this again right now and the <code>fields_attrs_query</code> should only run once per struct right? Afterwards it should be cached if im not mistaken right? Because if I'm checking this correctly right now it looks like this is being a lot of times? For the 1000 field struct case it's being executed 1001 times(cross crate cov_mark comes in really handy here)</del></p>



<a name="242794252"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/242794252" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#242794252">(Jun 15 2021 at 20:24)</a>:</h4>
<p><del>Which is definitely quadratic as it recollects all child fields again in each call for each field</del></p>



<a name="242794723"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/242794723" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#242794723">(Jun 15 2021 at 20:28)</a>:</h4>
<p><del>Exactly the same appears to be happening for <code>fields_attrs_source_map</code> so that explains the big time increases I got when commenting those out</del></p>



<a name="242794765"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/242794765" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#242794765">(Jun 15 2021 at 20:28)</a>:</h4>
<p><del>So I suppose salsa is kicking the results of those out of the cache immediately for some reason?</del></p>



<a name="242794812"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/242794812" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#242794812">(Jun 15 2021 at 20:29)</a>:</h4>
<p><del>Or not realizing that it can reuse the computation?(I dont really know how salsa works yet)</del></p>



<a name="242797957"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/242797957" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#242797957">(Jun 15 2021 at 20:52)</a>:</h4>
<p>oh wait the fixture generates one struct with n fields and n structs on the side nvm...</p>



<a name="242798144"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/242798144" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#242798144">(Jun 15 2021 at 20:53)</a>:</h4>
<p>I don't think I'll figure this out anytime soon,  I'm not making any progress with this <span aria-label="weary" class="emoji emoji-1f629" role="img" title="weary">:weary:</span></p>



<a name="243404117"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243404117" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243404117">(Jun 21 2021 at 15:59)</a>:</h4>
<p>Comming back to this! I've run the following bench in realease on the current master:</p>
<div class="codehilite"><pre><span></span><code>#[test]
fn benchmark_syntax_highlighting_long_struct() {
    for i in 0..=20 {
        let n = i * 500;
        let fixture = bench_fixture::big_struct_n(n);
        let (analysis, file_id) = fixture::file(&amp;fixture);
        let t = Instant::now();
        let _ = analysis.highlight(file_id);
        eprintln!(&quot;{:3} {:?}&quot;, i, t.elapsed());
    }
}
</code></pre></div>
<p>Here are the results:</p>
<div class="codehilite"><pre><span></span><code>  0 240.151µs
  1 37.874711ms
  2 110.355746ms
  3 217.256364ms
  4 361.15263ms
  5 539.999892ms
  6 756.224383ms
  7 1.005763744s
  8 1.294456419s
  9 1.616761095s
 10 1.979827698s
 11 2.367461069s
 12 2.820995648s
 13 3.273588743s
 14 3.767652556s
 15 4.308655111s
 16 4.941540713s
 17 5.605129736s
 18 6.257592457s
 19 6.927527017s
 20 7.656330973s
</code></pre></div>
<p>This is clearly quadratic -- doubling the number on the left quadruples the number on the right. 10 takes about 2s, 20 takes about 8s.</p>



<a name="243404650"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243404650" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243404650">(Jun 21 2021 at 16:03)</a>:</h4>
<p>Next fascinating observation: adding <code>return None</code> to the actual highlighting (<code>highlight::element</code> function)  doesn't change the timings at all. That it, whatever is slow in our syntax highlighting, it is clearly not the syntax highlighting!</p>



<a name="243405211"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243405211" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243405211">(Jun 21 2021 at 16:07)</a>:</h4>
<p>Yeah, commenting out all this doesn't change the picture: <a href="https://github.com/rust-analyzer/rust-analyzer/blob/1b05dbba39d5a4d46f321dc962df99038cddbf21/crates/ide/src/syntax_highlighting.rs#L286-L365">https://github.com/rust-analyzer/rust-analyzer/blob/1b05dbba39d5a4d46f321dc962df99038cddbf21/crates/ide/src/syntax_highlighting.rs#L286-L365</a></p>



<a name="243406143"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243406143" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243406143">(Jun 21 2021 at 16:14)</a>:</h4>
<p>Walking in from the other side, commenting the inside of the <code>for event in root.value.preorder_with_tokens() {</code> reveals that we have <em>two</em> indpendent sources of quadraticness here!</p>
<p>One is this block:</p>
<div class="codehilite" data-code-language="Rust"><pre><span></span><code><span class="w">        </span><span class="kd">let</span><span class="w"> </span><span class="n">element</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="k">match</span><span class="w"> </span><span class="n">event</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="n">WalkEvent</span>::<span class="n">Enter</span><span class="p">(</span><span class="n">it</span><span class="p">)</span><span class="w"> </span><span class="o">=&gt;</span><span class="w"> </span><span class="n">it</span><span class="p">,</span><span class="w"></span>
<span class="w">            </span><span class="n">WalkEvent</span>::<span class="n">Leave</span><span class="p">(</span><span class="n">it</span><span class="p">)</span><span class="w"> </span><span class="o">=&gt;</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                </span><span class="k">if</span><span class="w"> </span><span class="kd">let</span><span class="w"> </span><span class="nb">Some</span><span class="p">(</span><span class="n">node</span><span class="p">)</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">it</span><span class="p">.</span><span class="n">as_node</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                    </span><span class="n">inject</span>::<span class="n">doc_comment</span><span class="p">(</span><span class="n">hl</span><span class="p">,</span><span class="w"> </span><span class="n">sema</span><span class="p">,</span><span class="w"> </span><span class="n">root</span><span class="p">.</span><span class="n">with_value</span><span class="p">(</span><span class="n">node</span><span class="p">));</span><span class="w"></span>
<span class="w">                </span><span class="p">}</span><span class="w"></span>
<span class="w">                </span><span class="k">continue</span><span class="p">;</span><span class="w"></span>
<span class="w">            </span><span class="p">}</span><span class="w"></span>
<span class="w">        </span><span class="p">};</span><span class="w"></span>
</code></pre></div>
<p>The second one is this one:</p>
<div class="codehilite" data-code-language="Rust"><pre><span></span><code><span class="w">        </span><span class="k">match</span><span class="w"> </span><span class="n">event</span><span class="p">.</span><span class="n">clone</span><span class="p">().</span><span class="n">map</span><span class="p">(</span><span class="o">|</span><span class="n">it</span><span class="o">|</span><span class="w"> </span><span class="n">it</span><span class="p">.</span><span class="n">into_node</span><span class="p">().</span><span class="n">and_then</span><span class="p">(</span><span class="n">ast</span>::<span class="n">Item</span>::<span class="n">cast</span><span class="p">))</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="n">WalkEvent</span>::<span class="n">Enter</span><span class="p">(</span><span class="nb">Some</span><span class="p">(</span><span class="n">item</span><span class="p">))</span><span class="w"> </span><span class="o">=&gt;</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                </span><span class="k">if</span><span class="w"> </span><span class="n">sema</span><span class="p">.</span><span class="n">is_attr_macro_call</span><span class="p">(</span><span class="o">&amp;</span><span class="n">item</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                    </span><span class="n">current_attr_macro_call</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nb">Some</span><span class="p">(</span><span class="n">item</span><span class="p">);</span><span class="w"></span>
<span class="w">                </span><span class="p">}</span><span class="w"></span>
<span class="w">            </span><span class="p">}</span><span class="w"></span>
<span class="w">            </span><span class="n">WalkEvent</span>::<span class="n">Leave</span><span class="p">(</span><span class="nb">Some</span><span class="p">(</span><span class="n">item</span><span class="p">))</span><span class="w"> </span><span class="o">=&gt;</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                </span><span class="k">if</span><span class="w"> </span><span class="n">current_attr_macro_call</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="nb">Some</span><span class="p">(</span><span class="n">item</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                    </span><span class="n">current_attr_macro_call</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nb">None</span><span class="p">;</span><span class="w"></span>
<span class="w">                </span><span class="p">}</span><span class="w"></span>
<span class="w">            </span><span class="p">}</span><span class="w"></span>
<span class="w">            </span><span class="n">_</span><span class="w"> </span><span class="o">=&gt;</span><span class="w"> </span><span class="p">(),</span><span class="w"></span>
<span class="w">        </span><span class="p">}</span><span class="w"></span>
</code></pre></div>
<p>independently, each of those is O(N^2)</p>



<a name="243406772"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243406772" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243406772">(Jun 21 2021 at 16:19)</a>:</h4>
<p>hmm, what's the expected complexity of <code>Semantics::analyzer</code>?</p>



<a name="243407005"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243407005" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243407005">(Jun 21 2021 at 16:21)</a>:</h4>
<p><code>::analyze</code> ? I think cached <code>O(1)</code></p>



<a name="243407411"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243407411" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243407411">(Jun 21 2021 at 16:24)</a>:</h4>
<p>hmm, why is the attribute macro handling O(n²) then?</p>



<a name="243408017"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243408017" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243408017">(Jun 21 2021 at 16:29)</a>:</h4>
<p>Hm, somthing doesnt' make sense to me.. Heer's the code I've minimized this to:</p>
<div class="codehilite" data-code-language="Rust"><pre><span></span><code><span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">_it</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">stdx</span>::<span class="n">timeit</span><span class="p">(</span><span class="s">"total"</span><span class="p">);</span><span class="w"></span>
<span class="w">    </span><span class="k">for</span><span class="w"> </span><span class="n">event</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">root</span><span class="p">.</span><span class="n">value</span><span class="p">.</span><span class="n">preorder_with_tokens</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="kd">let</span><span class="w"> </span><span class="n">_it</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">stdx</span>::<span class="n">timeit</span><span class="p">(</span><span class="s">"loop"</span><span class="p">);</span><span class="w"></span>
<span class="w">        </span><span class="kd">let</span><span class="w"> </span><span class="n">element</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="k">match</span><span class="w"> </span><span class="n">event</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="n">WalkEvent</span>::<span class="n">Enter</span><span class="p">(</span><span class="n">it</span><span class="p">)</span><span class="w"> </span><span class="o">=&gt;</span><span class="w"> </span><span class="n">it</span><span class="p">,</span><span class="w"></span>
<span class="w">            </span><span class="n">WalkEvent</span>::<span class="n">Leave</span><span class="p">(</span><span class="n">it</span><span class="p">)</span><span class="w"> </span><span class="o">=&gt;</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                </span><span class="k">if</span><span class="w"> </span><span class="kd">let</span><span class="w"> </span><span class="nb">Some</span><span class="p">(</span><span class="n">node</span><span class="p">)</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">it</span><span class="p">.</span><span class="n">as_node</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">                    </span><span class="n">inject</span>::<span class="n">doc_comment</span><span class="p">(</span><span class="n">hl</span><span class="p">,</span><span class="w"> </span><span class="n">sema</span><span class="p">,</span><span class="w"> </span><span class="n">root</span><span class="p">.</span><span class="n">with_value</span><span class="p">(</span><span class="n">node</span><span class="p">));</span><span class="w"></span>
<span class="w">                </span><span class="p">}</span><span class="w"></span>
<span class="w">                </span><span class="k">continue</span><span class="p">;</span><span class="w"></span>
<span class="w">            </span><span class="p">}</span><span class="w"></span>
<span class="w">        </span><span class="p">};</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
</code></pre></div>
<p>And here's the output I get (filtering out times &lt; 2 ms):</p>
<div class="codehilite"><pre><span></span><code>loop: 655.68ms
total: 2.00s
 17 2.11564048s
loop: 713.26ms
total: 2.25s
 18 2.373231198s
loop: 788.57ms
total: 2.46s
 19 2.591156794s
loop: 859.33ms
total: 2.74s
 20 2.885021587s
</code></pre></div>
<p>There's only one slow loop here?</p>



<a name="243408251"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243408251" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243408251">(Jun 21 2021 at 16:31)</a>:</h4>
<p>Ah, no, it's just that rust is plenty fast -- individual loops to get into 0.3 ms range</p>



<a name="243408860"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243408860" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243408860">(Jun 21 2021 at 16:36)</a>:</h4>
<p>Apparetntly, both <code>to_def</code> and <code>.attrs</code> are quadratic</p>



<a name="243408898"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243408898" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243408898">(Jun 21 2021 at 16:37)</a>:</h4>
<p>Feels like a fractal, where each quadratic part consists of two independent quadratic parts</p>



<a name="243409101"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243409101" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243409101">(Jun 21 2021 at 16:39)</a>:</h4>
<p>So, <code>to_def</code> for RecordField is def linear...</p>



<a name="243409386"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243409386" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243409386">(Jun 21 2021 at 16:41)</a>:</h4>
<p>Thats roughly how far I got, but after that I got nowhere</p>



<a name="243409591"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243409591" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243409591">(Jun 21 2021 at 16:43)</a>:</h4>
<p>Yeah, I am now in the delightful <code>source_to_def</code> module. A good thing about it is that, once written, this module basically never changed. The bad  thing about it is that it's so tricky that it'd be better not have been written at all</p>



<a name="243409872"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243409872" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243409872">(Jun 21 2021 at 16:45)</a>:</h4>
<p>A fun thing, though, is that both Kotlin and Roslyn contain the code which does exactly the same -- it's a somwhat surprising essense of an ide it seems</p>



<a name="243410611"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243410611" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243410611">(Jun 21 2021 at 16:51)</a>:</h4>
<p>I have yet to understand that module to be honest</p>



<a name="243410624"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243410624" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243410624">(Jun 21 2021 at 16:51)</a>:</h4>
<p>Never really dug into it</p>



<a name="243411018"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243411018" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243411018">(Jun 21 2021 at 16:54)</a>:</h4>
<p>I am baffled that it has empty docs tbh, that's the interesting bit!(</p>



<a name="243411495"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243411495" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243411495">(Jun 21 2021 at 16:58)</a>:</h4>
<p>Curious! So, getting struct's source is linear...</p>



<a name="243411703"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243411703" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243411703">(Jun 21 2021 at 16:59)</a>:</h4>
<p>We have to many traits and to few "goto definition goes to impl" :(</p>



<a name="243411922"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243411922" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jeremy Kolb <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243411922">(Jun 21 2021 at 17:01)</a>:</h4>
<p>Does that include the fields in the struct? Your test above hints at it being related to the items</p>



<a name="243412392"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243412392" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243412392">(Jun 21 2021 at 17:05)</a>:</h4>
<p>Quadratic <code>SyntaxNodePtr</code>, I welcome you, my old friend!</p>
<div class="codehilite" data-code-language="Rust"><pre><span></span><code><span class="w">    </span><span class="k">pub</span><span class="w"> </span><span class="k">fn</span> <span class="nf">to_node</span><span class="p">(</span><span class="o">&amp;</span><span class="bp">self</span><span class="p">,</span><span class="w"> </span><span class="n">root</span>: <span class="kp">&amp;</span><span class="nc">SyntaxNode</span><span class="p">)</span><span class="w"> </span>-&gt; <span class="nc">SyntaxNode</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="fm">assert!</span><span class="p">(</span><span class="n">root</span><span class="p">.</span><span class="n">parent</span><span class="p">().</span><span class="n">is_none</span><span class="p">());</span><span class="w"></span>
<span class="w">        </span><span class="n">successors</span><span class="p">(</span><span class="nb">Some</span><span class="p">(</span><span class="n">root</span><span class="p">.</span><span class="n">clone</span><span class="p">()),</span><span class="w"> </span><span class="o">|</span><span class="n">node</span><span class="o">|</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">            </span><span class="n">node</span><span class="p">.</span><span class="n">children</span><span class="p">().</span><span class="n">find</span><span class="p">(</span><span class="o">|</span><span class="n">it</span><span class="o">|</span><span class="w"> </span><span class="n">it</span><span class="p">.</span><span class="n">text_range</span><span class="p">().</span><span class="n">contains_range</span><span class="p">(</span><span class="bp">self</span><span class="p">.</span><span class="n">range</span><span class="p">))</span><span class="w"></span>
<span class="w">        </span><span class="p">})</span><span class="w"></span>
<span class="w">        </span><span class="p">.</span><span class="n">find</span><span class="p">(</span><span class="o">|</span><span class="n">it</span><span class="o">|</span><span class="w"> </span><span class="n">it</span><span class="p">.</span><span class="n">text_range</span><span class="p">()</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="bp">self</span><span class="p">.</span><span class="n">range</span><span class="w"> </span><span class="o">&amp;&amp;</span><span class="w"> </span><span class="n">it</span><span class="p">.</span><span class="n">kind</span><span class="p">()</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="bp">self</span><span class="p">.</span><span class="n">kind</span><span class="p">)</span><span class="w"></span>
<span class="w">        </span><span class="p">.</span><span class="n">unwrap_or_else</span><span class="p">(</span><span class="o">||</span><span class="w"> </span><span class="fm">panic!</span><span class="p">(</span><span class="s">"can't resolve local ptr to SyntaxNode: {:?}"</span><span class="p">,</span><span class="w"> </span><span class="bp">self</span><span class="p">))</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
</code></pre></div>
<p>I've thought that this was fixed with transition to new rowan, but looks like it wasn't?</p>



<a name="243412650"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243412650" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243412650">(Jun 21 2021 at 17:07)</a>:</h4>
<p>oh wow</p>



<a name="243412699"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243412699" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243412699">(Jun 21 2021 at 17:07)</a>:</h4>
<p>that's going to be the most perf-improving one line change i've ever did</p>



<a name="243412715"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243412715" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243412715">(Jun 21 2021 at 17:07)</a>:</h4>
<p><span aria-label="tada" class="emoji emoji-1f389" role="img" title="tada">:tada:</span></p>



<a name="243413190"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243413190" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243413190">(Jun 21 2021 at 17:11)</a>:</h4>
<p>Good news: the change improves perf for n = 20 from 7.6s to 420ms. Bad news: some test hangs</p>



<a name="243413425"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243413425" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243413425">(Jun 21 2021 at 17:13)</a>:</h4>
<p>Correction: only good news is the real one! The tests that hangs is my manual very long quadratic test :D I sense an opportunity for an epic commit message</p>



<a name="243420494"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243420494" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243420494">(Jun 21 2021 at 18:05)</a>:</h4>
<p><a href="https://github.com/rust-analyzer/rust-analyzer/pull/9362/commits/099b63e7c01ed9969041bef8b3b9c573c7e24bf8">https://github.com/rust-analyzer/rust-analyzer/pull/9362/commits/099b63e7c01ed9969041bef8b3b9c573c7e24bf8</a></p>



<a name="243421987"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243421987" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jeremy Kolb <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243421987">(Jun 21 2021 at 18:17)</a>:</h4>
<p>it probably makes sense to doc comment <code>child_or_token_at_range</code> and mention that it performs a binary search</p>



<a name="243422246"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243422246" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243422246">(Jun 21 2021 at 18:19)</a>:</h4>
<p>yeah, nobody but Aleksey could have noticed this without docs</p>



<a name="243487420"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243487420" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243487420">(Jun 22 2021 at 08:46)</a>:</h4>
<p>Good call, added docs to rowan and ra. </p>
<p>To be fair, figuring out that this is linear is possible -- the original version used a hand-written naive linear search. </p>
<p>Figuring out that a faster version already exists in rowan and just needs to be enabled would be tricky, yeah</p>



<a name="243508399"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Syntax%20highlighting%20is%20quadratic/near/243508399" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Syntax.20highlighting.20is.20quadratic.html#243508399">(Jun 22 2021 at 12:32)</a>:</h4>
<p><a href="https://github.com/rust-analyzer/rust-analyzer/pull/9369/files">https://github.com/rust-analyzer/rust-analyzer/pull/9369/files</a> documents the magic source_to_def is</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>